package com.zwj.interview.DFS;



/**
 * 给定一棵二叉树和一个值sum，求二叉树中节点值之和等于sum的路径的数目。
 * 路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点，但不一定从根节点开始，
 * 也不一定到叶节点结束。例如，在如图8.5所示中的二叉树中有两条路径的节点值之和等于8，
 * 其中，第1条路径从节点5开始经过节点2到达节点1，第2条路径从节点2开始到节点6
 * <p>
 * 5
 * 2      4
 * <p>
 * 1   6   3  7
 */
public class 路径和等于目标值的个数again {


    /**
     * 如果在路径上移动时把所有累加的节点值之和都保存下来，就容易知道是否存在从任意节点出发的值为给定sum的路径。
     * 例如，当到达上图中二叉树的根节点5时，从根节点开始的路径节点值之和是5。当到达节点2时，
     * 从根节点开始的路径经过的节点值之和是7。当到达节点6时，从根节点出发到当前节点的路径经过的节点值之和为13。
     * 由于要找出节点值之和为8的路径，而13与5的差值是8，这就说明从节点5的下一个节点（即节点2）开始到节点6结束的路径经过的节点值之和为8
     *
     * @param root
     * @param targetSum
     * @return 有了前面的经验，就可以采用二叉树深度优先搜索来解决与路径相关的问题。当遍历到一个节点时，
     * 先累加从根节点开始的路径上的节点值之和，再计算到它的左右子节点的路径的节点值之和。这就是典型的前序遍历的顺序
     */
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
        //找出以root节点的路径数
        int res=rootSum(root,targetSum);
        //不断遍历左子树右子树，进行计算
        res+=rootSum(root.left,targetSum);
        res+=rootSum(root.right,targetSum);
        return res;
    }


    //表示以node为起点，路径和等于targetNum的路径条数
    public int rootSum(TreeNode root, int targetSum){
        int  res=0;
        if(root==null){
          return 0;
        }
        int val=root.val;
        if(val==targetSum){
            res++;
        }
        //不断递归左子树，找处和等于targetSum的路径条数
        res+=rootSum(root.left,targetSum);
        res+=rootSum(root.right,targetSum);
        return res;
    }




}
